package leetcodeHis;

import java.util.*;

public class P15ThreeNum {
    public static void main(String[] args) {
        int[] nums = {-2, 0, 1, 1, 2};
//        int[] numss = {-4, -1, -1, 0, 1, 2};
        for (List<Integer> integerList : threeSum2(nums)) {
            for (Integer integer : integerList) {
                System.out.print(integer);
            }
            System.out.println();
        }
    }

//    public  static List<List<Integer>> threeSum(int[] nums) {
//        for (int i = 0; i < nums.length; i++) {
//            List<Integer> list = twoSumN(nums, nums[i]);
//        }
//    }

    public static int[] twoSumN(int[] nums, int target) {
        int[] result = new int[2];
        HashMap<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            if(map.get(nums[i]) == null) {
                map.put(nums[i], i);
            }
            if(map.get(target - nums[i])!=null && map.get(target - nums[i])!=i) {
                result[0] = i;
                result[1] = map.get(target - nums[i]);
                return result;
            }
        }
        return result;
    }

//    public static  void add(List<Integer> result, int begin, int end, List<Integer> list) {
//        int search = 0 - list.get(begin) -  list.get(end);
//        list.remove(begin);
//        list.remove(end);
//        if(list.contains(search)) {
//            result.add(list.get(begin));
//            result.add(list.get(end));
//            result.add(search);
//        }
//    }
    /**
     * 每次从两边找，还是超出时间限制
     * @param nums
     * @return
     */
    public  static List<List<Integer>> threeSum3(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> parent = new ArrayList<>();
        if(nums.length == 0 || nums.length < 3) {return parent;}
        if(nums[0] == 0) {
            if(nums[0] + nums[1] + nums[2] == 0) {
                List<Integer> child = new ArrayList<>();
                child.add(0);
                child.add(0);
                child.add(0);
                parent.add(child);
                return parent;
            }
        }
        if(nums[0] > 0 ) {
            return parent;
        }
        Set<List<Integer>> set =new HashSet<>();
        int fir = 0;
        int sec = fir + 1;
        int third = nums.length-1;
        while (fir<third) {
            if(nums[fir] + nums[sec] + nums[third] == 0) {
                if(fir == sec || sec == third) {
                    break;
                }
                set.add(Arrays.asList(nums[fir], nums[sec], nums[third]));
                if(nums[fir] + nums[third] <= 0 ) {
                    fir += 1;
                    sec = fir+1;
                }
                if(nums[fir] + nums[third] > 0 ) {
                    third -= 1;
                    sec = third-1;
                }
            }else {
                if (nums[fir] + nums[third] < 0) {
                    if(nums[sec]< -(nums[fir] + nums[third])) {
                        fir += 1;
                        sec = fir + 1;
                    }
                }else if(nums[fir] + nums[third] >0) {
                    if(nums[sec]< -(nums[fir] + nums[third])) {
                        third -= 1;
                        sec = third - 1;
                    }
                }else {
                    sec += 1;
                }
            }
        }
        parent.addAll(set);
        return parent;
    }
//
//    public static List<Integer> threeS(int sum, int index, int[] nums) {
//
//    }



    /**
     * O(n^3)  超时
     * @param nums
     * @return
     */
    public  static List<List<Integer>> threeSum2(int[] nums) {
        Set<List<Integer>> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                for (int k = j+1; k < nums.length; k++) {
                    if(nums[i] + nums[j] + nums[k] == 0) {
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        Collections.sort(list);
                        set.add(Arrays.asList(new Integer[]{list.get(0), list.get(1), list.get(2)}));
                        list.removeAll(list);
                    }
                }
            }
        }
        List<List<Integer>> parent = new ArrayList<>();
        for (List<Integer> integers : set) {
            parent.add(integers);
        }
        return parent;
    }
}
